"""
Problem 32: https://projecteuler.net/problem=32

We shall say that an n-digit number is pandigital if it makes use of all the
digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through
5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing
multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can
be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only
include it once in your sum.
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/11
'''


def solution(D: int = 9) -> int:
    '''
    Find the sum of all products whose multiplicand/multiplier/product
     identity can be written as a 1 through 9 pandigital.

    assume, digits of a,b are d(a),d(b), 
    then for a*b, d(a*b) must be d(a)+d(b) or d(a)+d(b)-1.
    at the same time, d(a*b) + d(a) + d(b) = 9.
    so, d(a*b) = 4,  d(a)+d(b) = 5, such as 39 × 186 = 7254

    assume a < b, then d(a) <= d(b), 1 <= d(a) <=2, 3 <= d(b) <= 4
    d(a),d(b) maybe are (1,4),(2,3) 

    '''
    import math

    if D < 3:  # a,b,a*b must be difference digit
        return 0

    nanb = D//2 if D % 2 == 0 else D//2+1  # na+nb

    products = set()

    for a in range(2, 10**(nanb//2)):
        da = int(math.log10(a)) + 1
        db = nanb - da
        for b in range(int('123456789'[:db]), int('123456789'[-db:]) + 1):
            digits = set(str(a))
            digits.update(str(b) + str(a*b))
            if digits == set('123456789'[:D]):
                # print(f'{a*b} = {a} * {b}')
                products.add(a*b)

    return sum(products)


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 5901030
